class Tree:
    __name = 'Tree'

    ''' 向树中加入节点（集合） '''

    @staticmethod
    def add_node(tree=None, s=None):
        if s is None:  # 边为空
            return tree, 'error'
        if len(s) != 1:  # 一次只能加入一条边
            return tree, 'error'

        s_name = list(s.keys())[0]

        if tree is None:  # 树为空
            if len(s_name) != 2:
                return tree, 'error'
            if s_name[0] == s_name[1]:  # 起始点和终止点相同
                return tree, 'circle'
            new_tree = [[s_name[0], s_name[1]], s]  # 生成新树
            return new_tree, 'ok'

        v_set = tree[0]  # 树的边集
        s_set = tree[1]  # 树的点集
        if len(s_name) != 2:
            return tree, 'error'
        if s_name[0] == s_name[1]:  # 起始点和终止点相同
            return tree, 'circle'
        if s_name in s_set or s_name[::-1] in s_set:  # 边已经存在
            return tree, 'error'
        if s_name[0] in v_set and s_name[1] in v_set:  # 起始点和终止点都在树中，形成圈
            return tree, 'circle'
        if s_name[0] not in v_set and s_name[1] not in v_set:  # 起始点和终止点都不在树中，没有父节点
            return tree, 'not father'

        if s_name[0] not in v_set:  # 加入点
            v_set.append(s_name[0])
        if s_name[1] not in v_set:
            v_set.append(s_name[1])
        s_set.update(s)  # 加入边
        new_tree = [v_set, s_set]
        return new_tree, 'ok'

    ''' 将两棵树合并为森林（集合） '''

    @staticmethod
    def forest_tree(tree1=None, tree2=None, s=None):
        v_set1 = tree1[0]
        v_set2 = tree2[0]
        if list(set(v_set1) & set(v_set2)):  # 顶点有交集，不是森林
            return tree1, 'error'
        if len(s) != 1:  # 只能有一个桥
            return tree1, 'error'

        s_name = list(s.keys())[0]

        if len(s_name) != 2:
            return tree1, 'error'
        if s_name[0] == s_name[1]:
            return tree1, 'error'
        if (s_name[0] in v_set1 and s_name[1] in v_set2) or (s_name[1] in v_set1 and s_name[0] in v_set2):
            v_set = tree1[0] + tree2[0]
            s_set = tree1[1]
            s_set.update(tree2[1])
            s_set.update(s)
            return [v_set, s_set], 'ok'

        return tree1, 'error'

    ''' 节点或边是否在树中（集合） '''

    @staticmethod
    def in_tree(tree=None, v=None, s=None):
        if tree is None:
            return False
        if v is not None:  # 点在点集中
            return v in tree[0]
        if s is not None:  # 边在边集中
            return s in tree[1]
        return False
